package leetcode;

/**
 * @author caifangyi
 * @date 2022/8/8
 */

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 761. 特殊的二进制序列
 *
 *
 * 特殊的二进制序列是具有以下两个性质的二进制序列：
 *
 * 0 的数量与 1 的数量相等。
 * 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
 * 给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
 *
 * 在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
 *
 * 示例 1:
 *
 * 输入: S = "11011000"
 * 输出: "11100100"
 * 解释:
 * 将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
 * 这是在进行若干次操作后按字典序排列最大的结果。
 * 说明:
 *
 * S 的长度不超过 50。
 * S 保证为一个满足上述定义的特殊 的二进制序列。
 */
class Day0761 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s1 = solution.makeLargestSpecial("11011000");
        System.out.println(s1.equals("11100100"));
        String s2 = solution.makeLargestSpecial("11100010");
        System.out.println(s2.equals("11100010"));
        String s3 = solution.makeLargestSpecial("101100101100");
        System.out.println(s3.equals("110011001010"));

    }

    /**
     * 把1看作左括号'(', 0看作右括号')',
     * 字典排序最大把最多个完整括号的组合放到最前面
     * 11011000 -》 ( () (()) ) -> ( (()) () ) -> 11100100
     */
    static class Solution {
        public String makeLargestSpecial(String s) {

            Deque<String> deque = new ArrayDeque<>();
            Deque<String> temp = new ArrayDeque<>();
            for (int i = 0; i < s.length(); i++) {
                //如果是左括号，压栈
                boolean ifLeft = s.charAt(i) == '1';
                if(ifLeft){
                    deque.push("1");
                    continue;
                }

                //提取中间值
                while (deque.peekFirst().length() > 1){
                    temp.push(deque.pollFirst());
                }

                //如果是右括号，出栈并拼成一个完整的括号组合
                String left = deque.pollFirst();

                StringBuilder sb = new StringBuilder();
                sb.append(left);
                //插入中间值
                while (!temp.isEmpty()){
                    sb.append(temp.pollFirst());
                }
                sb.append("0");

                //括号组合压入栈, 并排序
                while (!deque.isEmpty()
                        && deque.peekFirst().length() > 1
                        && sb.toString().compareTo(deque.peekFirst()) > 0){
                    temp.push(deque.pollFirst());
                }

                deque.push(sb.toString());
                while (!temp.isEmpty()){
                    deque.push(temp.pollFirst());
                }

            }
            while (!temp.isEmpty()) {
                deque.push(temp.pollFirst());
            }
            StringBuilder sb = new StringBuilder();
            while(!deque.isEmpty()){
                sb.append(deque.pollLast());
            }
            return sb.toString();
        }
    }
}
